// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// Min Heap是表示最小堆的结构
type MinHeap struct {
	heapArray []int // 存储堆元素的数组
	size      int   // 堆中的当前元素数
	maxsize   int   // 堆可以容纳的最大元素数
}

// newMinHeap 返回具有指定最大大小的 MinHeap 的新实例
func newMinHeap(maxsize int) *MinHeap {
	MinHeap := &MinHeap{
		heapArray: []int{},
		size:      0,
		maxsize:   maxsize,
	}
	return MinHeap
}

// 如果给定索引是叶节点，则 leaf 返回 true，否则返回 false
func (m *MinHeap) leaf(index int) bool {
	if index >= (m.size/2) && index <= m.size {
		return true
	}
	return false
}

// parent 返回给定索引的父节点的索引
func (m *MinHeap) parent(index int) int {
	return (index - 1) / 2
}

// leftchild 返回给定索引的左子节点的索引
func (m MinHeap) leftchild(index int) int {
	return 2*index + 1
}

// rightchild 返回给定索引的右子节点的索引
func (m MinHeap) rightchild(index int) int {
	return 2*index + 2
}

// insert 向堆中添加一个新元素
func (m *MinHeap) insert(item int) error {
	if m.size >= m.maxsize {
		return fmt.Errorf("Heap is full")
	}
	m.heapArray = append(m.heapArray, item)
	m.size++
	m.upHeapify(m.size - 1)
	return nil
}

// swap 交换两个给定索引处的元素
func (m *MinHeap) swap(first, second int) {
	temp := m.heapArray[first]
	m.heapArray[first] = m.heapArray[second]
	m.heapArray[second] = temp
}

// upHeapify 将给定索引处的元素向上移动到堆中，直到它位于正确的位置
func (m *MinHeap) upHeapify(index int) {
	for m.heapArray[index] < m.heapArray[m.parent(index)] {
		m.swap(index, m.parent(index))
		index = m.parent(index)
	}
}

// downHeapify 将给定索引处的元素向下移动到堆中，直到它位于正确的位置
func (m *MinHeap) downHeapify(current int) {
	if m.leaf(current) {
		return
	}
	smallest := current
	leftChildIndex := m.leftchild(current)
	rightRightIndex := m.rightchild(current)

	if leftChildIndex < m.size && m.heapArray[leftChildIndex] < m.heapArray[smallest] {
		smallest = leftChildIndex
	}
	if rightRightIndex < m.size && m.heapArray[rightRightIndex] < m.heapArray[smallest] {
		smallest = rightRightIndex
	}
	if smallest != current {
		m.swap(current, smallest)
		m.downHeapify(smallest)
	}
	return
}

// buildMinHeap 通过在所有非叶子节点上自下而上调用 downHeapify 来构建最小堆
func (m *MinHeap) buildMinHeap() {
	for index := ((m.size / 2) - 1); index >= 0; index-- {
		m.downHeapify(index)
	}
}

// remove 从堆中移除最小元素
func (m *MinHeap) remove() int {
	top := m.heapArray[0]
	m.heapArray[0] = m.heapArray[m.size-1]
	m.heapArray = m.heapArray[:(m.size)-1]
	m.size--
	m.downHeapify(0)
	return top
}

func main() {
	inputArray := []int{1, 6, 8, 9, 66, 88}
	minHeap := newMinHeap(len(inputArray))
	for i := 0; i < len(inputArray); i++ {
		minHeap.insert(inputArray[i])
	}
	minHeap.buildMinHeap()
	for i := 0; i < len(inputArray); i++ {
		fmt.Println(minHeap.remove())
	}
}

//$ go run minHeap.go
//1
//6
//8
//9
//66
//88
